
#ifndef __list_h__
#define __list_h__

#include "types.h"

/**
 * @file
 * Das Modul list.h exportiert eine Datenstruktur für listen samt
 * einer Auswahl an nützlichen Funktionen.
 *
 * <h3>Beschreibung</h3>
 * Eine Liste besteht lediglich aus einem Kopfelement. Alle Knoten
 * sind wie in einem Ring miteinander verbunden, so dass das 
 * jeweils erste oder letzte Element auf das Kopfelement zeigt. Ist
 * die Liste leer, zeigt dieses Kopfelement auf sich selbst.
 * (Dies erlaubt eine sehr einfache und effiziente Implementierung
 *  der verschiedenen Listenfunktionen)
 */

/**
 * Listenknoten fuer doppelt verkettete Listen.
 */
typedef struct list_node_t {
    struct list_node_t *prev; ///< Zeiger auf vorherigen Listenknoten
    struct list_node_t *next; ///< Zeiger auf nachfolgenden Listenknoten
} list_node_t;

/**
 * Listen typ um (zumindest visuell) zwischen Knoten und Knotenelement
 * zu unterscheiden.
 */
typedef list_node_t list;

/**
 * list_empty überprüft ob die Liste leer ist
 *
 * @param l : Zeiger auf Liste
 * @return TRUE, wenn Liste leer ist
 */
int 
list_empty(list *l);

/**
 * list_node_init initialisiert einen Knoten bevor er das erste mal
 * verwendet werden kann.
 *
 * @param node : zu initialisierender Listenknoten
 *
 * @return Zeiger auf initialisierten Listenknoten
 */
list_node_t *
list_node_init(list_node_t *node);

/**
 * list_init Initialisiere eine leere Liste, die anschließen 
 * gefüllt werden kann
 *
 * @param node : zu initialisierender Listenknoten
 *
 * @return Zeiger auf initialisierten Listenknoten
 */
#define list_init(l) list_node_init(l)

/**
 * list_add_after Fuegt einen neuen Knoten hinter dem aktuellen Knoten ein.
 *
 * @param node : Knoten nach dem eingefuegt werden soll
 * @param new_node : neuer Knoten, der eingefuegt werden soll 
 *                   (darf in keiner Liste stehen)
 */
void 
list_add_after(list_node_t *node, list_node_t *new_node);

/**
 * list_add_before Fuegt neuen Knoten vor aktuellen Knoten in Liste ein.
 *
 * @param node : Knoten, vor dem eingefuegt werden soll
 * @param new_node : neuer einzufuegender Knoten
 */
void 
list_add_before(list_node_t *node, list_node_t *new_node);

/**
 * Haengt einen Knoten an das Ender der Liste an.
 *
 * @param list : Liste
 * @param new_node : Knoten der angefuegt werden soll
 *
 * @return Eingabeliste
 */
list *
list_append(list *list, list_node_t *new_node);

/**
 * Fuegt Knoten an den Anfang der Liste ein und gibt Zeiger auf Liste zurueck.
 *
 * @param list : Liste
 * @param new_node : Knoten der angefuegt werden soll
 *
 * @return Eingabeliste
 */
list *
list_prepend(list *list, list_node_t *new_node);

/**
 * list_is_last überprüft ob der gegebene Knoten das letzte Element der
 * Liste ist.
 *
 * @param list : Liste
 * @param node : zu üperprüfender Knoten
 *
 * @return True, wenn Knoten letztes Element
 */
BOOL 
list_is_last(list *list, list_node_t *node);

/**
 * list_is_first überprüft ob der gegebene Knoten das erste Element der
 * Liste ist.
 *
 * @param list : Liste
 * @param node : zu üperprüfender Knoten
 *
 * @return True, wenn Knoten erstes Element
 */
BOOL 
list_is_first(list *list, list_node_t *node);

/**
 * list_len1 überprüft, ob die Liste genau 1 Element enthält.
 *
 * @param list : Liste
 *
 * @return True, wenn Liste genau 1 Element enthält
 */
BOOL 
list_len1(list *list);

/**
 * list_concat hängt die Elemente der zweiten Liste an die Zielliste an.
 *
 * <b>Vorsicht: aus der zweiten Liste werden alle Knoten entfernt</b>
 *
 * @param dest : Zielliste
 * @param src : Liste, die angehängt werden soll
 *
 * @return Zeiger auf Zielliste
 */
list *
list_concat(list *dest, list *src);

/**
 * list_push fuegt Knoten an den Anfang der Liste ein und gibt Zeiger auf Liste zurueck.
 *
 * @param list : Liste
 * @param new_node : Knoten der angefuegt werden soll
 *
 * @return Eingabeliste
 */
#define list_push(node, new_node) list_prepend(node, new_node)

/**
 * Entfernt gegebenen Knoten aus seiner Liste. 
 * <b>
 * Wenn Knoten in keiner Liste enthalten ist, ist das Verhalten undefiniert.
 * </b>
 *
 * @param current : Knoten, der entfernt werden soll
 *
 * @return Zeiger auf gegebenen Knoten
 */
list_node_t *
list_remove(list_node_t *current);

/**
 * list_pop Entfernt erstes Element aus der Liste und gibt dieses zurueck.
 * Wenn die Liste leer ist, dann wird NULL zurueckgegeben.
 *
 * @param : die Liste
 *
 * @return entfernter Listenknoten oder NULL, wenn Liste leer ist
 */
list_node_t *
list_pop(list *list);

/**
 * list_first ermittelt das erste Element in der Liste.
 *
 * @param list : Liste
 *
 * @return Zeiger auf den ersten Knoten der Liste (NULL, wenn Liste leer)
 */
list_node_t *
list_first(list *list);

/**
 * list_last ermittelt das letzte Element in der Liste.
 *
 * @param list : Liste
 *
 * @return Zeiger auf den letzten Knoten der Liste (NULL, wenn Liste leer)
 */
list_node_t *
list_last(list *list);

#define list_entry(node, kind, member) (((kind*)node)->member)

#define list_foreach(var, head, member) \
	for(var = (typeof(*var)*) (head)->next; \
	    (list_node*)(var) != head; \
        var = (typeof(*var)*) ((list_node*)(&(var)->member))->next )


#define list_reverse_foreach(var, head, member) \
    for(var = (typeof(*var)*) (head)->prev; \
        (list_node*)(var) != head; \
        var = (typeof(*var)*) ((list_node*)(&(var)->member))->prev)

#define list_foreach_p(var, head, member, pred) \
	list_foreach(var, head, member) if(pred) 

#endif
